package monoqueue;

import java.util.LinkedList;
import java.util.Stack;

/**
 * @author pengfei.hpf
 * @date 2020/3/2
 * @verdion 1.0.0
 * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
 *
 * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
 *
 *  
 *
 *
 *
 * 以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。
 *
 *  
 *
 *
 *
 * 图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。
 *
 *  
 *
 * 示例:
 *
 * 输入: [2,1,5,6,2,3]
 * 输出: 10
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/largest-rectangle-in-histogram
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LargestRectangleArea {

    public int largestRectangleArea(int[] heights) {
        if(heights == null || heights.length == 0){
            return 0;
        }
        Stack<Integer> stack = new Stack<>();
        int max = 0;
        stack.push(-1);
        for(int i = 0; i < heights.length; i ++){
            int num = heights[i];
            while(stack.peek() != -1 && num < heights[stack.peek()]){
                max = Math.max(max, heights[stack.pop()] * (i - stack.peek() - 1));
            }
            stack.push(i);
        }
        while(stack.peek() != -1){
            max = Math.max(max, heights[stack.pop()] * (heights.length - stack.peek() -1));
        }
        return max;
    }


    public static void main(String[] args){
        System.out.println((new LargestRectangleArea()).largestRectangleArea(new int[]{2,1,5,6,2,3}));
    }
}
